package algorithm.dynamicProgramming.p354;

import java.util.Arrays;

/**
 * 354. 俄罗斯套娃信封问题
 */
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        // 信封第一位是宽度，第二位是高度
        // 将信封按照宽度进行升序排列，如果宽度相等，再按照高度进行降序排列
        // 因为两个宽度相同的信封不能相互包含，宽度相同时将高度逆序排列，
        // 则这些逆序高度中最多只有一个被选入递增子序列，保证了最终的信封序列中不会出现宽度相同的情况
        Arrays.sort(envelopes, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        // 在高度上统计最长递增子序列的长度
        return lengthOfLIS(envelopes);
    }

    private int lengthOfLIS(int[][] envelopes) {
        // dp[[i]为以nums[i][1]为结尾的最长递增子序列的长度
        int n = envelopes.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = dp[0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (res < dp[i])
                res = dp[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
        System.out.println(new Solution().maxEnvelopes(envelopes));
    }
}